Method: evaluateDiagonals(VierConnectsBoard, VierConnectsFieldState, boolean)

1: package de.fhdw.gaming.ipspiel24.VierConnects.strategy.minimax;
2:
3: import java.util.ArrayList;
4: import java.util.Arrays;
5: import java.util.List;
6: import java.util.Optional;
7:
8: import de.fhdw.gaming.core.domain.GameException;
9: import de.fhdw.gaming.ipspiel24.VierConnects.core.domain.VierConnectsBoard;
10: import de.fhdw.gaming.ipspiel24.VierConnects.core.domain.VierConnectsFieldState;
11: import de.fhdw.gaming.ipspiel24.VierConnects.core.domain.VierConnectsPlayer;
12: import de.fhdw.gaming.ipspiel24.VierConnects.core.domain.VierConnectsPosition;
13: import de.fhdw.gaming.ipspiel24.VierConnects.core.domain.VierConnectsState;
14: import de.fhdw.gaming.ipspiel24.VierConnects.core.domain.VierConnectsStrategy;
15: import de.fhdw.gaming.ipspiel24.VierConnects.core.moves.VierConnectsMove;
16: import de.fhdw.gaming.ipspiel24.VierConnects.core.moves.factory.VierConnectsMoveFactory;
17: import de.fhdw.gaming.ipspiel24.minimax.Minimax;
18: import de.fhdw.gaming.ipspiel24.minimax.MinimaxStrategy;
19:
20: /**
21: * Minimax Strategy for VierConnects.
22: */
23: public class VierConnectsMinimaxStrategy implements VierConnectsStrategy,
24: MinimaxStrategy<VierConnectsPlayer, VierConnectsState, VierConnectsMove> {
25:
26: /**
27: * the moveFactory.
28: */
29: private final VierConnectsMoveFactory moveFactory;
30:
31: // maxDepth of Search Tree
32: private final int maxDepth = 5;
33:
34: // multiplier for centre positions
35: private final int scoreCenterCountMultiplier = 2;
36:
37: // scores for player evaluation
38: private final int scoreWin = 999999;
39: private final int score3Row = 100;
40: private final int score2Row = 50;
41:
42: // scores for enemy evaluation
43: //these need to be positive numbers, as they get subtracted from the score.
44: private final int scoreLose = 99999;
45: private final int score3RowEnemy = 100;
46:
47: /**
48: * constructor.
49: *
50: * @param moveFactory public moveFactory.
51: */
52: public VierConnectsMinimaxStrategy(VierConnectsMoveFactory moveFactory) {
53: this.moveFactory = moveFactory;
54: }
55:
56: @Override
57: public Optional<VierConnectsMove> computeNextMove(int gameId, VierConnectsPlayer player, VierConnectsState state,
58: long maxComputationTimePerMove) throws GameException, InterruptedException {
59: // long startTime = System.nanoTime(); //left these in case i want to measure time again for something
60: final VierConnectsPlayer opponent = this.getOpponent(state);
61: final Minimax<VierConnectsPlayer, VierConnectsState,
62: VierConnectsMove> minimax = new Minimax<VierConnectsPlayer, VierConnectsState, VierConnectsMove>(this,
63: this.maxDepth, opponent);
64: final VierConnectsMove bestMove = minimax.getBestMove(state, player);
65: // long endTime = System.nanoTime();
66: // System.out.print((endTime - startTime) + ";");
67: return Optional.of(bestMove);
68: }
69:
70: @Override
71: public List<VierConnectsMove> getPossibleMoves(VierConnectsState state) {
72:
73: final List<VierConnectsMove> possibleMoves = new ArrayList<>();
74: final VierConnectsBoard board = state.getBoard();
75: for (int i = 0; i < board.getColumnSize(); i++) {
76: final VierConnectsPosition pos = VierConnectsPosition.of(0, i);
77: if (board.getFieldAt(pos).getState() == VierConnectsFieldState.EMPTY) {
78: possibleMoves.add(moveFactory.createPlaceMarkMove(
79: state.getCurrentPlayer().isUsingCrosses(), i));
80: }
81: }
82:
83: return orderMoves(possibleMoves);
84: }
85:
86: /**
87: * takes possibleMoves in a List and orders it to start from the middle.
88: * e.g.: 0,1,2,3,4,5,6,7 -> 3,4,2,5,1,6,0,7
89: * (prioritise better Moves for more effective alpha- beta-pruning)
90: *
91: * @param possibleMoves list of ordered possibleMoves left to right
92: * @return new ordered list of possible Moves starting from the beginning.
93: */
94: private List<VierConnectsMove> orderMoves(List<VierConnectsMove> possibleMoves) {
95: List<VierConnectsMove> orderedMoves = new ArrayList<>(possibleMoves.size());
96: int middle = possibleMoves.size() / 2;
97:
98: for (int i = 0; i < possibleMoves.size(); i++) {
99: int index = middle + (i % 2 == 0 ? i / 2 : -(i / 2 + 1));
100: orderedMoves.add(possibleMoves.get(index));
101: }
102:
103: return orderedMoves;
104: }
105:
106: /**
107: * evaluates window of four positions and gives score for 2,3,4 in a row.
108: * also gives bas score for good opponent position.
109: *
110: * @param window array of four fields (the state of the fields)
111: * @param playerState the state of the player that is using minimax
112: * @return score of window.
113: */
114: private int evaluateWindow(VierConnectsFieldState[] window, VierConnectsFieldState playerState) {
115: int score = 0;
116:
117: final VierConnectsFieldState opponent = this.getOpponent(playerState);
118:
119: final long playerCount = Arrays.stream(window).filter(p -> p == playerState).count();
120: final long opponentCount = Arrays.stream(window).filter(p -> p == opponent).count();
121: final long emptyCount = Arrays.stream(window).filter(p -> p == VierConnectsFieldState.EMPTY).count();
122:
123: if (playerCount == 4) {
124: score += this.scoreWin;
125: } else if (playerCount == 3 && emptyCount == 1) {
126: score += this.score3Row;
127: } else if (playerCount == 2 && emptyCount == 2) {
128: score += this.score2Row;
129: }
130:
131: if (opponentCount == 4) {
132: score -= this.scoreLose;
133: } else if (opponentCount == 3 && emptyCount == 1) {
134: score -= this.score3RowEnemy;
135: }
136:
137: return score;
138: }
139:
140: /**
141: * returns a score for all rows or columns.
142: *
143: * @param board board Board of the current State that gets evaluated.
144: * @param playerState State of the current Player
145: * @param isColumn boolean whether rows or columns get evaluated.
146: * @return score for all rows or columns
147: */
148: private int evaluateDirection(VierConnectsBoard board, VierConnectsFieldState playerState, boolean isColumn) {
149: int score = 0;
150: final int primarySize = isColumn ? board.getColumnSize() : board.getRowSize();
151: final int secondarySize = isColumn ? board.getRowSize() : board.getColumnSize();
152:
153: for (int primary = 0; primary < primarySize; primary++) {
154: final VierConnectsFieldState[] array = new VierConnectsFieldState[secondarySize];
155: for (int secondary = 0; secondary < secondarySize; secondary++) {
156: final VierConnectsPosition position = isColumn ? VierConnectsPosition.of(secondary, primary)
157: : VierConnectsPosition.of(primary, secondary);
158: array[secondary] = board.getFieldAt(position).getState();
159: }
160: for (int secondary = 0; secondary < secondarySize - 3; secondary++) {
161: final VierConnectsFieldState[] window = Arrays.copyOfRange(array, secondary, secondary + 4);
162: score += evaluateWindow(window, playerState);
163: }
164: }
165:
166: return score;
167: }
168:
169: /**
170: * returns a score for all (positive or negative) diagonal positions.
171: *
172: * @param board Board of the current State that gets evaluated.
173: * @param playerState State of the current Player
174: * @param isPositiveSlope boolean whether the negative or positive slopes get evaluated.
175: * @return score for positive or negative positions.
176: */
177: private int evaluateDiagonals(VierConnectsBoard board, VierConnectsFieldState playerState,
178: boolean isPositiveSlope) {
179: int score = 0;
180: final int rowSize = board.getRowSize();
181: final int columnSize = board.getColumnSize();
182:
183:• for (int r = 0; r < rowSize - 3; r++) {
184:• for (int c = 0; c < columnSize - 3; c++) {
185: final VierConnectsFieldState[] window = new VierConnectsFieldState[4];
186:• for (int i = 0; i < 4; i++) {
187:• if (isPositiveSlope) {
188: window[i] = board.getFieldAt(VierConnectsPosition.of(r + i, c + i)).getState();
189: } else {
190: window[i] = board.getFieldAt(VierConnectsPosition.of(r + 3 - i, c + i)).getState();
191: }
192: }
193: score += evaluateWindow(window, playerState);
194: }
195: }
196:
197: return score;
198: }
199:
200: @Override
201: public int evaluate(VierConnectsState state, VierConnectsPlayer player, int depth) {
202: int score = 0;
203:
204: final VierConnectsBoard board = state.getBoard();
205: final int columnSize = board.getColumnSize();
206: final int rowSize = board.getRowSize();
207: final VierConnectsFieldState playerState = player.isUsingCrosses() ? VierConnectsFieldState.CROSS
208: : VierConnectsFieldState.NOUGHT;
209:
210: // score for middle position
211: int centerCount = 0;
212: for (int r = 0; r < rowSize; r++) {
213: if (board.getFieldAt(VierConnectsPosition.of(r, columnSize / 2)).getState() == playerState) {
214: centerCount++;
215: }
216: }
217: score += centerCount * this.scoreCenterCountMultiplier;
218: // score for depth
219: score += this.maxDepth - depth;
220:
221: // Evaluate columns
222: score += evaluateDirection(board, playerState, true);
223:
224: // Evaluate rows
225: score += evaluateDirection(board, playerState, false);
226:
227: // Evaluate positive sloped diagonals
228: score += evaluateDiagonals(board, playerState, true);
229:
230: // Evaluate negative sloped diagonals
231: score += evaluateDiagonals(board, playerState, false);
232:
233: return score;
234: }
235:
236: @Override
237: public VierConnectsPlayer getOpponent(VierConnectsState state) {
238: return state.getCurrentPlayer() == state.getCrossesPlayer()
239: ? state.getNoughtsPlayer()
240: : state.getCrossesPlayer();
241: }
242:
243: /**
244: * returns the opponent FieldState for a given VierConnectsFieldState.
245: *
246: * @param state FieldState of the current Player.
247: * @return opposite State of the given fieldState.
248: */
249: public VierConnectsFieldState getOpponent(VierConnectsFieldState state) {
250: return state.equals(VierConnectsFieldState.CROSS) ? VierConnectsFieldState.NOUGHT
251: : VierConnectsFieldState.CROSS;
252: }
253:
254: @Override
255: public String toString() {
256: return "Vier-Gewinnt Minimax Strategy";
257: }
258:
259: }